package offer53_2;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int missingNumber(int[] nums) {
        if(nums[0]!=0){
            return 0;
        }
        if(nums[nums.length-1]== nums.length-1)
            return nums.length;
        int size = nums.length;
        int left = 0;
        int right = size - 1;
        if (right == left) {
            if(nums[0]==0)
                return 1;
            if(nums[0]==1)
                return 0;
        }
        while (right - left > 1) {

            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) {
                //[left,mid]，缺失一定在
                right = mid;
            } else {
                //右边有数据缺失
                left = mid;
            }
        }

        return left + 1;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int[] arr = {1,2};
        int res = new Solution().missingNumber(arr);
        System.out.println(res);
    }
}
